/**
 *
 *
 * Matching problem.
 *
 * <h2>Definitions:</h2>
 * <p>Given graph $G=(V,E)$.</p>
 * <ul>
 *     <li>Matching $M$ is a set of non-adjacent edges (i.e. no two edges have common vertices). $M ⊆ E$.
 *     <li>A vertex $v$ is <strong>exposed</strong> (or <strong>unmatched</strong>) if it's not attached to any edge in $M$.
 *     <li>A vertex $v$ is <strong>matched</strong> (or <strong>saturated</strong>) if it's attached to any edge in $M$.
 *     <li>An <strong>$X$-saturating matching</strong> is a match which covers all the vertices in $X$.
 *     <li>Matching $M$ is <strong>maximal</strong> if we cannot add any more edge to $M$.
 *     <li>Matching $M$ is <strong>maximum</strong> if it contains the largest possible number of edges. Maximum matching is also maximal.
 *      <p><img src="../../../../../images/maximal_vs_maximum_matching.svg" alt="Maximal vs Miximum Matching">
 *     <li>Matching $M$ is <strong>perfect</strong> (or <strong>complete</strong>) if it covers all vertices. Perfect matching is also maximum and maximal.
 *     <li>An <strong>alternating</strong> path contains matching and non-matching edges alternatively.
 *     <li>An <strong>augmenting</strong> path is an alternating path where both end vertices are exposed.
 *      <p><img src="../../../../../images/augmenting_path.svg" alt="Augmenting Path">
 * </ul>
 *
 * <p><strong>Berge's Theorem</strong>: A matched graph $(G, M)$ has augmenting path iff $M$ is not maximum.
 *
 * <p>It's easy to see that if there is an augmenting path, we can flip the edge to increase the number of edge in $M$ by one while maintaining the matching condition.
 *
 * <pre> 0 ───── 1 ═════ 2 ───── 3 ═════ 4 ───── 5   →  0 ═════ 1 ───── 2 ═════ 3 ───── 4 ═════ 5 </pre>
 *
 * <p> We use the annotation $M⊗P$ to mean a graph derived from the original grah by augmenting path $P$ to $M$.
 *
 * <h3>Bipartite Matching Problem</h3>
 * <p>Bipartite matching problem is easier to crack than non bipartite problem. So it's mentioned
 * first. Given graph $G=(V,E)=(A,B;E)$, the graph is partitioned into $A$, $B$</p>
 *
 * <p><strong>Hall's Marriage Theorem</strong>: a bipartite graph $G = (A,B;E)$ has $A$-saturating matching iff $A$ satisfies marriage condition: $|S| ≤ |N(S)| ∀ S ⊆ A$ where $N(S) ⊆ B$ is the neighbouring set of $S$. Basically, any subset of girls in $A$ likes at least as large set of boys in $B$.
 *
 * <p>Proof by induction: This is true for $|A|=1$. For cases of $|A| ≥ 2$, if all subset $S$ is strictly larger than $N(S)$, then we pair a girl in $A$ with a boy in $B$ and remove them from the graph, the marriage condition still holds for the remaining boys and girls, so we can match the rest of girls by induction. If there exists a subset of girls $X ⊆ A$ that likes the same-size subset of boys $Y ⊆ B$ (i.e. $|X| = |Y|$), we match all girls in $X$ with all boys in $Y$ and remove them from the graph. We need to show that the marriage condition still holds for the remaining girls and boys (i.e. the remaining grap $G'=(A-X, B-Y, E')$ still satisfies the marriange condition). In this remaining graph, let take any subset $X' ⊆ A-X$, and let $Y' = N(X')$. We need to show that $|X'| ≤ |Y'|$. Look at the original graph $G$, the combined set of girls $X ⋃ X'$ like the set of boys $Y ⋃ Y'$, so $|X ⋃ X'| ≤ |Y ⋃ Y'|$. As we remove $X$ from the left and equal-size $Y$ from the right, $|X'| ≤ |Y'|$.
 *
 * <p><strong>Hall's Threorem Collary</strong>: A bipartite is regular if every vertex on left has the same degree $c$ and every vertex on the right has the same degree $d$. A regular bipartite $G = (A,B,E)$ has a matching for the vertices on $A$ if $c ≥ d &lt; 0$.
 *
 * <p><strong>Konig's Theorem</strong>: For any bipartite graph, the maximum size of a matching = the minimum size of vertex cover.</p>
 *
 * <p>To find the maximum matching, one can use different algorithms such as max flow ($O(mn)$ time) and augmenting paths. In this section, I present
 * the augmenting path algorithm because it also helps finding the minimum vertex cover. Finding both maximum matching and minimum
 * vertex cover is helpful for Hungarian algorithm later.</p>
 *
 * <p>The algorithm to find augmenting paths:</p>
 * <ul>
 *     <li>Build directed graph $D=(V,E*)$ where the edge is directed from $A$ to $B$ if it's not in $M$ and from $B$ to $A$ if it's in $M$.</li>
 *     <li>Do depth first search from all exposed vertices in $A$ till it hits an exposed vertex in $B$.</li>
 *     <li>If such path is found where it starts from an exposed vertex in $A$ to an exposed vertex in $B$, the path is an augmenting path. Fix the augmenting path to increase matching set $M$.</li>
 *     <li>Repeat until no augmenting path is found, the matching $M$ is a maximum match. Do the same depth-first-search steps above for all the exposed vertices in $A$. Let set $L$ be the set of all the vertices found by this step. Then $C=(A-L)⋃(B⋂L)$ is the minimum vertex cover.</li>
 * </ul>
 * <p><img src="../../../../../images/bipartite_matching.svg" alt="Bipartite Matching algorithm">
 * <p>The running time is $O(nm)$, but if several augmenting paths are found simultaneously (as in Hopcroft-Karp algorithm), the running time is reduced to $O(√nm)$.
 *
 * <p>The augmenting path algorithm has one interesting property: after $k$ step, there are $k$ edges in the matching $M$ because each step, $|M|$ is increased by 1.
 *
 * <p><strong>Hopcroft-Karp algorithm:</strong>
 *
 * <p>Similar to augmenting path algorithm, but instead of finding one augmenting path at a time, Hopcroft-Karp algorithm tries to find maximal <strong>set</strong> of vertex-disjoint <strong>shortest</strong>augmenting paths, reducing the running time to $O(√nm)$.
 *
 * <p><strong>Alternating Trees:</strong>
 * <p>Another method to find augmenting path is to build alternating trees. To be continued.</p>
 *
 *
 *
 * <p><strong>Applications</strong>
 *
 * <p>Latin Square: given a Latin Square with the first few rows filled with numbers. Prove that we can always fill the remaining rows in the Latin Square.
 *
 * <pre>
 *         ┌───┬───┬───┬───┬───┐        ┌───┬───┬───┬───┬───┐
 *         │ 1 │ 2 │ 3 │ 4 │ 5 │        │ 1 │ 2 │ 3 │ 4 │ 5 │
 *         ├───┼───┼───┼───┼───┤        ├───┼───┼───┼───┼───┤
 *         │ 5 │ 4 │ 2 │ 1 │ 3 │        │ 5 │ 4 │ 2 │ 1 │ 3 │
 *         ├───┼───┼───┼───┼───┤        ├───┼───┼───┼───┼───┤
 *         │ 4 │ 3 │ 5 │ 2 │ 1 │        │ 4 │ 3 │ 5 │ 2 │ 1 │
 *         ├───┼───┼───┼───┼───┤        ├───┼───┼───┼───┼───┤
 *         │   │   │   │   │   │        │ 3 │ 1 │ 4 │ 5 │ 2 │
 *         ├───┼───┼───┼───┼───┤        ├───┼───┼───┼───┼───┤
 *         │   │   │   │   │   │        │ 2 │ 5 │ 1 │ 3 │ 4 │
 *         └───┴───┴───┴───┴───┘        └───┴───┴───┴───┴───┘
 * </pre>
 *
 * <p>We will need to use Hall's Collary. Construct a graph $G=(A,B;E) where each column represent a vertex in $A$ and each number in {1,...,n} represent vertex in $B$. For every node in $A$, consider all the remaining numbers that the corresponding column has not used, we make an edge from the node to all these numbers in $B$. Now, we need to find a matching from $A$ to $B$. From Hall's Collary, we can always find such matching. The resulted matching will be the numbers for next row. We keep doing this until all the rows are filled. 
 *
 *
 * <h2>Weighted bipatite matching.</h2>
 *
 * <p>General goal: find matching with maximum total weights. However, we can focus on finding perfect matching with total weights problem because we can always reduce other cases into this case. For example, add dummy edge with negative value small enough, or add dummy vertex to make equal-size partitions. Also, we can assume no negative weight edge as we can always add a constant to all the weights without changing the matching. Moreover, the minimum problem can also be converted to maximum problem by negate all the edges' weights.
 *
 * <p>Given: graph $G=(A,B;E)$ where $|A| = |B|$ and $w_e ≥ 0 ∀ e ∈ E$.
 * <p>Goal: find perfect matching with maximum total weights.
 *
 * <p>See {@link net.tp.algo.assignment} for linear programming and Hungarian methods of finding maximum matching for weighted bipartite matching.
 *
 * <p><strong>Negative cycle algorithm:</strong>
 *
 * <p>Let $M$ be a perfect matching. Build directed graph $D(M)=(A,B;E*)$ where edge will point from $A$ to $B$ if the edge belongs to $M$ and from $B$ to $A$ if the edge does not belong to $M$. Also, the edge $e$ has weight $w_e$ if $e ∈ M$ and of $-w_e$ if $e ∉ M$.
 *
 * <p>Theorem: The perfect matching $M$ has maximum weight iff there is no negative cycle in $D$.
 *
 * <p>Algorithm:
 * <ul>
 *  <li>Find perfect matching $M$ in $G$
 *  <li>While there is negative weight cycle in $D$, fix the negative cycle.
 * </ul>
 *
 * <p>To find negative cycle, use Floyd-Warshall algorithm which takes $O(n^3)$. Let $W$ be the largest edge weight. The maximum possible weight for $M$ is $nW$, so the algorithm ends at most $nW$ iterations. The total running time is $O(n^4W)$.
 * 
 * <p>This algorithm is not polynomial because $W$ can be large and each iteration, we assume that the weight increases by one. To make this algorithm a polynomial algorithm, we need to find larger weight increment in each iteration. (see Edmonds and Karp, 1972, Theoretical Improvements in Algorithmic Efficiency for Network Flow).
 *
 * <p><img src="../../../../../images/weighted_bipartite_matching.svg" alt="Weighted Bipartite Matching algorithm">
 *
 *
 * <p><strong>Augmenting Path Algorithm (Kuhn's algorithm or Hungarian method):</strong>
 *
 * <p>As noted above, each step in augmenting path algorithm increases the match by 1 edge. So the idea is to use augmenting path to find the maximum weight matching with exactly $k+1$ edges given the maximum weight matching with exactly $k$ edges. Then by induction, we can find the maximum weight matching.
 *
 * <p>Given the maximum weight matching $M_k$ with exactly $k$ edges, we will need to find an augmenting path that maximizes the net weight increase.
 *
 * <p>Build directed graph $D(M_k)=(A,B;E*)$ where edge will point from $A$ to $B$ if the edge belongs to $M$ and from $B$ to $A$ if the edge does not belong to $M$. Also, the edge $e$ has weight $w_e$ if $e ∈ M$ and of $-w_e$ if $e ∉ M$.
 *
 * <p>To find an augmenting path that maximize the net weight increase, we need to find the shortest augmenting path between two unmatched nodes. This is a multiple-source shortest path problem. We need to convert into single-source shortest path problem by adding a dummy node for source and a dummy node for target.
 *
 * <p>Before getting to the implementation details, let's see why finding the shortest augmenting path of $M_k$ will result in the maximum weight matching $M_{k+1}$. Let $P$ be the shortest path in $D(M)$ with length $l(P)$, then
 *
 * <p>$w(M⊗P) = w(M) - w(P ⋂ M) + w(P - M) = w(M) - l(P)$
 *
 * <p>So to maximize $w(M⊗P)$, we need to minimize $l(P)$.
 *
 * <p>Note that there is no negative cycle in $D(M_k)$ because if there is negative cycle, we would have fixed the negative cycle to get a higher weight matching with exactly $k$ edges. This means that we can use Bellman-Ford to find shortest path.
 *
 * <p style="overflow:auto"><img src="../../../../../images/weighted_bipartite_matching_augment.svg" alt="Weighted Bipartite Matching algorithm"></p>
 *
 * <p>Running time: To find $k$-edge matching, we need to do $k$ iteration, each iteration cost $O(mn)$ using Bellman-Ford, so the total running time is $O(kmn)$. If the task is to find perfect matching, $k=n$ and $m=O(n^2)$, the total running time is $O(n^4)$.
 *
 *
 *
 *
 * @author Trung Phan
 *
 */
package net.tp.algo.matching;
